<!DOCTYPE html>
<html lang="zh-CN">
    <!-- title -->




<!-- keywords -->




<head><meta name="generator" content="Hexo 3.9.0">
    <meta charset="utf-8">
    <meta name="viewport" content="width=device-width, initial-scale=1.0, user-scalable=no">
    <meta name="author" content="XQ">
    <meta name="renderer" content="webkit">
    <meta name="copyright" content="XQ">
    
    <meta name="keywords" content="红黑树,iOS,Android,RN,Web,晴风">
    
    <meta name="description" content>
    <meta name="description" content="#include &quot;main.h&quot;  using namespace std;  int main(int argc, char *argv[]) {     RBT *rbt = new RBT();      int n = 0;     cin &amp;gt;&amp;gt; n;     for (int i = 0; i &amp;lt; n; ++i) {         int temp = 0;         c">
<meta name="keywords" content="红黑树">
<meta property="og:type" content="article">
<meta property="og:title" content="红黑树的实现">
<meta property="og:url" content="https://blog.xq99.org/posts/6.红黑树的实现/index.html">
<meta property="og:site_name" content="晴风的博客">
<meta property="og:description" content="#include &quot;main.h&quot;  using namespace std;  int main(int argc, char *argv[]) {     RBT *rbt = new RBT();      int n = 0;     cin &amp;gt;&amp;gt; n;     for (int i = 0; i &amp;lt; n; ++i) {         int temp = 0;         c">
<meta property="og:locale" content="zh-CN">
<meta property="og:updated_time" content="2020-12-03T06:32:45.000Z">
<meta name="twitter:card" content="summary">
<meta name="twitter:title" content="红黑树的实现">
<meta name="twitter:description" content="#include &quot;main.h&quot;  using namespace std;  int main(int argc, char *argv[]) {     RBT *rbt = new RBT();      int n = 0;     cin &amp;gt;&amp;gt; n;     for (int i = 0; i &amp;lt; n; ++i) {         int temp = 0;         c">
    <meta http-equiv="Cache-control" content="no-cache">
    <meta http-equiv="X-UA-Compatible" content="IE=edge,chrome=1">
    
    <link rel="alternate" href="/atom.xml" title="晴风的博客" type="application/atom+xml">
    
    <title>红黑树的实现 · 晴风的博客</title>
    <style type="text/css">
    @font-face {
        font-family: 'Oswald-Regular';
        src: url("/font/Oswald-Regular.ttf");
    }

    body {
        margin: 0;
    }

    header,
    footer,
    .back-top,
    .sidebar,
    .container,
    .site-intro-meta,
    .toc-wrapper {
        display: none;
    }

    .site-intro {
        position: relative;
        z-index: 3;
        width: 100%;
        /* height: 50vh; */
        overflow: hidden;
    }

    .site-intro-placeholder {
        position: absolute;
        z-index: -2;
        top: 0;
        left: 0;
        width: calc(100% + 300px);
        height: 100%;
        background: repeating-linear-gradient(-45deg, #444 0, #444 80px, #333 80px, #333 160px);
        background-position: center center;
        transform: translate3d(-226px, 0, 0);
        animation: gradient-move 2.5s ease-out 0s infinite;
    }

    @keyframes gradient-move {
        0% {
            transform: translate3d(-226px, 0, 0);
        }
        100% {
            transform: translate3d(0, 0, 0);
        }
    }

</style>

    <link rel="preload" href="/css/style.css?v=20180824" as="style" onload="this.onload=null;this.rel='stylesheet'">
    <link rel="stylesheet" href="/css/mobile.css?v=20180824" media="(max-width: 980px)">
    
    <link rel="preload" href="https://cdnjs.cloudflare.com/ajax/libs/fancybox/3.2.5/jquery.fancybox.min.css" as="style" onload="this.onload=null;this.rel='stylesheet'">
    
    <!-- /*! loadCSS. [c]2017 Filament Group, Inc. MIT License */
/* This file is meant as a standalone workflow for
- testing support for link[rel=preload]
- enabling async CSS loading in browsers that do not support rel=preload
- applying rel preload css once loaded, whether supported or not.
*/ -->
<script>
(function( w ){
	"use strict";
	// rel=preload support test
	if( !w.loadCSS ){
		w.loadCSS = function(){};
	}
	// define on the loadCSS obj
	var rp = loadCSS.relpreload = {};
	// rel=preload feature support test
	// runs once and returns a function for compat purposes
	rp.support = (function(){
		var ret;
		try {
			ret = w.document.createElement( "link" ).relList.supports( "preload" );
		} catch (e) {
			ret = false;
		}
		return function(){
			return ret;
		};
	})();

	// if preload isn't supported, get an asynchronous load by using a non-matching media attribute
	// then change that media back to its intended value on load
	rp.bindMediaToggle = function( link ){
		// remember existing media attr for ultimate state, or default to 'all'
		var finalMedia = link.media || "all";

		function enableStylesheet(){
			link.media = finalMedia;
		}

		// bind load handlers to enable media
		if( link.addEventListener ){
			link.addEventListener( "load", enableStylesheet );
		} else if( link.attachEvent ){
			link.attachEvent( "onload", enableStylesheet );
		}

		// Set rel and non-applicable media type to start an async request
		// note: timeout allows this to happen async to let rendering continue in IE
		setTimeout(function(){
			link.rel = "stylesheet";
			link.media = "only x";
		});
		// also enable media after 3 seconds,
		// which will catch very old_post browsers (android 2.x, old_post firefox) that don't support onload on link
		setTimeout( enableStylesheet, 3000 );
	};

	// loop through link elements in DOM
	rp.poly = function(){
		// double check this to prevent external calls from running
		if( rp.support() ){
			return;
		}
		var links = w.document.getElementsByTagName( "link" );
		for( var i = 0; i < links.length; i++ ){
			var link = links[ i ];
			// qualify links to those with rel=preload and as=style attrs
			if( link.rel === "preload" && link.getAttribute( "as" ) === "style" && !link.getAttribute( "data-loadcss" ) ){
				// prevent rerunning on link
				link.setAttribute( "data-loadcss", true );
				// bind listeners to toggle media back
				rp.bindMediaToggle( link );
			}
		}
	};

	// if unsupported, run the polyfill
	if( !rp.support() ){
		// run once at least
		rp.poly();

		// rerun poly on an interval until onload
		var run = w.setInterval( rp.poly, 500 );
		if( w.addEventListener ){
			w.addEventListener( "load", function(){
				rp.poly();
				w.clearInterval( run );
			} );
		} else if( w.attachEvent ){
			w.attachEvent( "onload", function(){
				rp.poly();
				w.clearInterval( run );
			} );
		}
	}


	// commonjs
	if( typeof exports !== "undefined" ){
		exports.loadCSS = loadCSS;
	}
	else {
		w.loadCSS = loadCSS;
	}
}( typeof global !== "undefined" ? global : this ) );
</script>

    <link rel="icon" href="/assets/favicon.png">
    <link rel="preload" href="https://cdn.jsdelivr.net/npm/webfontloader@1.6.28/webfontloader.min.js" as="script">
    <link rel="preload" href="https://cdn.jsdelivr.net/npm/jquery@3.3.1/dist/jquery.min.js" as="script">
    <link rel="preload" href="/scripts/main.js" as="script">
    <link rel="preload" as="font" href="/font/Oswald-Regular.ttf" crossorigin>
    <link rel="preload" as="font" href="https://at.alicdn.com/t/font_327081_1dta1rlogw17zaor.woff" crossorigin>
    
    <!-- fancybox -->
    <script src="https://cdnjs.cloudflare.com/ajax/libs/fancybox/3.2.5/jquery.fancybox.min.js" defer></script>
    <!-- 百度统计  -->
    
    <!-- 谷歌统计  -->
    
<link rel="stylesheet" href="/css/prism-tomorrow.css" type="text/css"></head>

    
        <body class="post-body">
    
    
<header class="header">

    <div class="read-progress"></div>
    <div class="header-sidebar-menu">&#xe775;</div>
    <!-- post页的toggle banner  -->
    
    <div class="banner">
            <div class="blog-title">
                <a href="/" >晴风的博客</a>
            </div>
            <div class="post-title">
                <a href="#" class="post-name">红黑树的实现</a>
            </div>
    </div>
    
    <a class="home-link" href=/>晴风的博客</a>
</header>
    <div class="wrapper">
        <div class="site-intro" style="







height:24vh;
">
    
    <!-- 主页  -->
    
    
    <!-- 404页  -->
            
    <div class="site-intro-placeholder"></div>
    <div class="site-intro-img" style="background-image: url(/intro/index-bg.jpg)"></div>
    <div class="site-intro-meta">
        <!-- 标题  -->
        <h1 class="intro-title">
            <!-- 主页  -->
            
            红黑树的实现
            <!-- 404 -->
            
        </h1>
        <!-- 副标题 -->
        <p class="intro-subtitle">
            <!-- 主页副标题  -->
            
            
            <!-- 404 -->
            
        </p>
        <!-- 文章页meta -->
        
            <div class="post-intros">
                <!-- 文章页标签  -->
                
                    <div class= post-intro-tags >
    
        <a class="post-tag" href="javascript:void(0);" data-tags = "C++">C++</a>
    
        <a class="post-tag" href="javascript:void(0);" data-tags = "数据结构">数据结构</a>
    
        <a class="post-tag" href="javascript:void(0);" data-tags = "红黑树">红黑树</a>
    
</div>
                
                
                    <div class="post-intro-read">
                        <span>字数统计: <span class="post-count word-count">1.3k</span>阅读时长: <span class="post-count reading-time">8 min</span></span>
                    </div>
                
                <div class="post-intro-meta">
                    <span class="post-intro-calander iconfont-archer">&#xe676;</span>
                    <span class="post-intro-time">2020/12/03</span>
                    
                    <span id="busuanzi_container_page_pv" class="busuanzi-pv">
                        <span class="iconfont-archer">&#xe602;</span>
                        <span id="busuanzi_value_page_pv"></span>
                    </span>
                    
                    <span class="shareWrapper">
                        <span class="iconfont-archer shareIcon">&#xe71d;</span>
                        <span class="shareText">Share</span>
                        <ul class="shareList">
                            <li class="iconfont-archer share-qr" data-type="qr">&#xe75b;
                                <div class="share-qrcode"></div>
                            </li>
                            <li class="iconfont-archer" data-type="weibo">&#xe619;</li>
                            <li class="iconfont-archer" data-type="qzone">&#xe62e;</li>
                            <li class="iconfont-archer" data-type="twitter">&#xe634;</li>
                            <li class="iconfont-archer" data-type="facebook">&#xe67a;</li>
                        </ul>
                    </span>
                </div>
            </div>
        
    </div>
</div>
        <script>
 
  // get user agent
  var browser = {
    versions: function () {
      var u = window.navigator.userAgent;
      return {
        userAgent: u,
        trident: u.indexOf('Trident') > -1, //IE内核
        presto: u.indexOf('Presto') > -1, //opera内核
        webKit: u.indexOf('AppleWebKit') > -1, //苹果、谷歌内核
        gecko: u.indexOf('Gecko') > -1 && u.indexOf('KHTML') == -1, //火狐内核
        mobile: !!u.match(/AppleWebKit.*Mobile.*/), //是否为移动终端
        ios: !!u.match(/\(i[^;]+;( U;)? CPU.+Mac OS X/), //ios终端
        android: u.indexOf('Android') > -1 || u.indexOf('Linux') > -1, //android终端或者uc浏览器
        iPhone: u.indexOf('iPhone') > -1 || u.indexOf('Mac') > -1, //是否为iPhone或者安卓QQ浏览器
        iPad: u.indexOf('iPad') > -1, //是否为iPad
        webApp: u.indexOf('Safari') == -1, //是否为web应用程序，没有头部与底部
        weixin: u.indexOf('MicroMessenger') == -1, //是否为微信浏览器
        uc: u.indexOf('UCBrowser') > -1 //是否为android下的UC浏览器
      };
    }()
  }
  console.log("userAgent:" + browser.versions.userAgent);

  // callback
  function fontLoaded() {
    console.log('font loaded');
    if (document.getElementsByClassName('site-intro-meta')) {
      document.getElementsByClassName('intro-title')[0].classList.add('intro-fade-in');
      document.getElementsByClassName('intro-subtitle')[0].classList.add('intro-fade-in');
      var postIntros = document.getElementsByClassName('post-intros')[0]
      if (postIntros) {
        postIntros.classList.add('post-fade-in');
      }
    }
  }

  // UC不支持跨域，所以直接显示
  function asyncCb(){
    if (browser.versions.uc) {
      console.log("UCBrowser");
      fontLoaded();
    } else {
      WebFont.load({
        custom: {
          families: ['Oswald-Regular']
        },
        loading: function () {  //所有字体开始加载
          // console.log('loading');
        },
        active: function () {  //所有字体已渲染
          fontLoaded();
        },
        inactive: function () { //字体预加载失败，无效字体或浏览器不支持加载
          console.log('inactive: timeout');
          fontLoaded();
        },
        timeout: 5000 // Set the timeout to two seconds
      });
    }
  }

  function asyncErr(){
    console.warn('script load from CDN failed, will load local script')
  }

  // load webfont-loader async, and add callback function
  function async(u, cb, err) {
    var d = document, t = 'script',
      o = d.createElement(t),
      s = d.getElementsByTagName(t)[0];
    o.src = u;
    if (cb) { o.addEventListener('load', function (e) { cb(null, e); }, false); }
    if (err) { o.addEventListener('error', function (e) { err(null, e); }, false); }
    s.parentNode.insertBefore(o, s);
  }

  var asyncLoadWithFallBack = function(arr, success, reject) {
      var currReject = function(){
        reject()
        arr.shift()
        if(arr.length)
          async(arr[0], success, currReject)
        }

      async(arr[0], success, currReject)
  }

  asyncLoadWithFallBack([
    "https://cdn.jsdelivr.net/npm/webfontloader@1.6.28/webfontloader.min.js", 
    "https://cdn.bootcss.com/webfont/1.6.28/webfontloader.js",
    "/lib/webfontloader.min.js"
  ], asyncCb, asyncErr)
</script>        
        <img class="loading" src="/assets/loading.svg" style="display: block; margin: 6rem auto 0 auto; width: 6rem; height: 6rem;" />
        <div class="container container-unloaded">
            <main class="main post-page">
    <article class="article-entry">
        <pre class=" language-cpp"><code class="language-cpp"><span class="token macro property">#<span class="token directive keyword">include</span> <span class="token string">"main.h"</span></span>

<span class="token keyword">using</span> <span class="token keyword">namespace</span> std<span class="token punctuation">;</span>

<span class="token keyword">int</span> <span class="token function">main</span><span class="token punctuation">(</span><span class="token keyword">int</span> argc<span class="token punctuation">,</span> <span class="token keyword">char</span> <span class="token operator">*</span>argv<span class="token punctuation">[</span><span class="token punctuation">]</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
    RBT <span class="token operator">*</span>rbt <span class="token operator">=</span> <span class="token keyword">new</span> <span class="token function">RBT</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>

    <span class="token keyword">int</span> n <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span>
    cin <span class="token operator">>></span> n<span class="token punctuation">;</span>
    <span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">int</span> i <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span> i <span class="token operator">&lt;</span> n<span class="token punctuation">;</span> <span class="token operator">++</span>i<span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token keyword">int</span> temp <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span>
        cin <span class="token operator">>></span> temp<span class="token punctuation">;</span>
        rbt<span class="token operator">-</span><span class="token operator">></span><span class="token function">add</span><span class="token punctuation">(</span><span class="token keyword">new</span> <span class="token function">RBTNode</span><span class="token punctuation">(</span>temp<span class="token punctuation">,</span> <span class="token keyword">nullptr</span><span class="token punctuation">,</span> <span class="token keyword">nullptr</span><span class="token punctuation">,</span> <span class="token keyword">nullptr</span><span class="token punctuation">,</span> <span class="token string">"R"</span><span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token punctuation">}</span>

    rbt<span class="token operator">-</span><span class="token operator">></span><span class="token function">preOrder</span><span class="token punctuation">(</span>rbt<span class="token operator">-</span><span class="token operator">></span><span class="token function">getRoot</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
    cout <span class="token operator">&lt;&lt;</span> endl<span class="token punctuation">;</span>
    rbt<span class="token operator">-</span><span class="token operator">></span><span class="token function">inOrder</span><span class="token punctuation">(</span>rbt<span class="token operator">-</span><span class="token operator">></span><span class="token function">getRoot</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
    cout <span class="token operator">&lt;&lt;</span> endl<span class="token punctuation">;</span>
    rbt<span class="token operator">-</span><span class="token operator">></span><span class="token function">postOrder</span><span class="token punctuation">(</span>rbt<span class="token operator">-</span><span class="token operator">></span><span class="token function">getRoot</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
    cout <span class="token operator">&lt;&lt;</span> endl<span class="token punctuation">;</span>
    rbt<span class="token operator">-</span><span class="token operator">></span><span class="token function">levelOrder</span><span class="token punctuation">(</span>rbt<span class="token operator">-</span><span class="token operator">></span><span class="token function">getRoot</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
    cout <span class="token operator">&lt;&lt;</span> endl<span class="token punctuation">;</span>


    <span class="token keyword">while</span> <span class="token punctuation">(</span>cin <span class="token operator">>></span> n<span class="token punctuation">)</span> <span class="token punctuation">{</span>
        RBTNode <span class="token operator">*</span>p <span class="token operator">=</span> rbt<span class="token operator">-</span><span class="token operator">></span><span class="token function">get</span><span class="token punctuation">(</span>n<span class="token punctuation">)</span><span class="token punctuation">;</span>
        rbt<span class="token operator">-</span><span class="token operator">></span><span class="token function">erase</span><span class="token punctuation">(</span>p<span class="token punctuation">)</span><span class="token punctuation">;</span>
        rbt<span class="token operator">-</span><span class="token operator">></span><span class="token function">preOrder</span><span class="token punctuation">(</span>rbt<span class="token operator">-</span><span class="token operator">></span><span class="token function">getRoot</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
        cout <span class="token operator">&lt;&lt;</span> endl<span class="token punctuation">;</span>
        rbt<span class="token operator">-</span><span class="token operator">></span><span class="token function">inOrder</span><span class="token punctuation">(</span>rbt<span class="token operator">-</span><span class="token operator">></span><span class="token function">getRoot</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
        cout <span class="token operator">&lt;&lt;</span> endl<span class="token punctuation">;</span>
        rbt<span class="token operator">-</span><span class="token operator">></span><span class="token function">postOrder</span><span class="token punctuation">(</span>rbt<span class="token operator">-</span><span class="token operator">></span><span class="token function">getRoot</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
        cout <span class="token operator">&lt;&lt;</span> endl<span class="token punctuation">;</span>
        rbt<span class="token operator">-</span><span class="token operator">></span><span class="token function">levelOrder</span><span class="token punctuation">(</span>rbt<span class="token operator">-</span><span class="token operator">></span><span class="token function">getRoot</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
        cout <span class="token operator">&lt;&lt;</span> endl<span class="token punctuation">;</span>
    <span class="token punctuation">}</span>

    <span class="token keyword">delete</span> rbt<span class="token punctuation">;</span>

<span class="token punctuation">}</span>
</code></pre>
<pre class=" language-cpp"><code class="language-cpp"><span class="token comment" spellcheck="true">//</span>
<span class="token comment" spellcheck="true">// Created by XQ on 2020/4/29.</span>
<span class="token comment" spellcheck="true">//</span>

<span class="token macro property">#<span class="token directive keyword">include</span> <span class="token string">"RBTNode.h"</span></span>

RBTNode<span class="token operator">::</span><span class="token function">RBTNode</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>

<span class="token punctuation">}</span>


RBTNode<span class="token operator">::</span><span class="token function">RBTNode</span><span class="token punctuation">(</span><span class="token keyword">int</span> value<span class="token punctuation">)</span> <span class="token punctuation">{</span>
    <span class="token keyword">this</span><span class="token operator">-</span><span class="token operator">></span>value <span class="token operator">=</span> value<span class="token punctuation">;</span>
<span class="token punctuation">}</span>


RBTNode<span class="token operator">::</span><span class="token function">RBTNode</span><span class="token punctuation">(</span><span class="token keyword">int</span> value<span class="token punctuation">,</span> RBTNode <span class="token operator">*</span>parent<span class="token punctuation">,</span> RBTNode <span class="token operator">*</span>left<span class="token punctuation">,</span> RBTNode <span class="token operator">*</span>right<span class="token punctuation">,</span> string color<span class="token punctuation">)</span> <span class="token punctuation">{</span>
    <span class="token keyword">this</span><span class="token operator">-</span><span class="token operator">></span>value <span class="token operator">=</span> value<span class="token punctuation">;</span>
    <span class="token keyword">this</span><span class="token operator">-</span><span class="token operator">></span>parent <span class="token operator">=</span> parent<span class="token punctuation">;</span>
    <span class="token keyword">this</span><span class="token operator">-</span><span class="token operator">></span>left <span class="token operator">=</span> left<span class="token punctuation">;</span>
    <span class="token keyword">this</span><span class="token operator">-</span><span class="token operator">></span>right <span class="token operator">=</span> right<span class="token punctuation">;</span>
    <span class="token keyword">this</span><span class="token operator">-</span><span class="token operator">></span>color <span class="token operator">=</span> color<span class="token punctuation">;</span>
<span class="token punctuation">}</span>


RBTNode<span class="token operator">::</span><span class="token operator">~</span><span class="token function">RBTNode</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
    <span class="token keyword">this</span><span class="token operator">-</span><span class="token operator">></span>value <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span>
    <span class="token keyword">this</span><span class="token operator">-</span><span class="token operator">></span>parent <span class="token operator">=</span> <span class="token keyword">nullptr</span><span class="token punctuation">;</span>
    <span class="token keyword">this</span><span class="token operator">-</span><span class="token operator">></span>left <span class="token operator">=</span> <span class="token keyword">nullptr</span><span class="token punctuation">;</span>
    <span class="token keyword">this</span><span class="token operator">-</span><span class="token operator">></span>right <span class="token operator">=</span> <span class="token keyword">nullptr</span><span class="token punctuation">;</span>
<span class="token punctuation">}</span>


<span class="token keyword">int</span> RBTNode<span class="token operator">::</span><span class="token function">getValue</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
    <span class="token keyword">return</span> <span class="token keyword">this</span><span class="token operator">-</span><span class="token operator">></span>value<span class="token punctuation">;</span>
<span class="token punctuation">}</span>


<span class="token keyword">void</span> RBTNode<span class="token operator">::</span><span class="token function">setValue</span><span class="token punctuation">(</span><span class="token keyword">int</span> value<span class="token punctuation">)</span> <span class="token punctuation">{</span>
    <span class="token keyword">this</span><span class="token operator">-</span><span class="token operator">></span>value <span class="token operator">=</span> value<span class="token punctuation">;</span>
<span class="token punctuation">}</span>


RBTNode <span class="token operator">*</span>RBTNode<span class="token operator">::</span><span class="token function">getParent</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
    <span class="token keyword">return</span> <span class="token keyword">this</span><span class="token operator">-</span><span class="token operator">></span>parent<span class="token punctuation">;</span>
<span class="token punctuation">}</span>


<span class="token keyword">void</span> RBTNode<span class="token operator">::</span><span class="token function">setParent</span><span class="token punctuation">(</span>RBTNode <span class="token operator">*</span>parent<span class="token punctuation">)</span> <span class="token punctuation">{</span>
    <span class="token keyword">this</span><span class="token operator">-</span><span class="token operator">></span>parent <span class="token operator">=</span> parent<span class="token punctuation">;</span>
<span class="token punctuation">}</span>


RBTNode <span class="token operator">*</span>RBTNode<span class="token operator">::</span><span class="token function">getLeft</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
    <span class="token keyword">return</span> <span class="token keyword">this</span><span class="token operator">-</span><span class="token operator">></span>left<span class="token punctuation">;</span>
<span class="token punctuation">}</span>


<span class="token keyword">void</span> RBTNode<span class="token operator">::</span><span class="token function">setLeft</span><span class="token punctuation">(</span>RBTNode <span class="token operator">*</span>left<span class="token punctuation">)</span> <span class="token punctuation">{</span>
    <span class="token keyword">this</span><span class="token operator">-</span><span class="token operator">></span>left <span class="token operator">=</span> left<span class="token punctuation">;</span>
<span class="token punctuation">}</span>


RBTNode <span class="token operator">*</span>RBTNode<span class="token operator">::</span><span class="token function">getRight</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
    <span class="token keyword">return</span> <span class="token keyword">this</span><span class="token operator">-</span><span class="token operator">></span>right<span class="token punctuation">;</span>
<span class="token punctuation">}</span>


<span class="token keyword">void</span> RBTNode<span class="token operator">::</span><span class="token function">setRight</span><span class="token punctuation">(</span>RBTNode <span class="token operator">*</span>right<span class="token punctuation">)</span> <span class="token punctuation">{</span>
    <span class="token keyword">this</span><span class="token operator">-</span><span class="token operator">></span>right <span class="token operator">=</span> right<span class="token punctuation">;</span>
<span class="token punctuation">}</span>


string RBTNode<span class="token operator">::</span><span class="token function">getColor</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
    <span class="token keyword">return</span> <span class="token keyword">this</span><span class="token operator">-</span><span class="token operator">></span>color<span class="token punctuation">;</span>
<span class="token punctuation">}</span>


<span class="token keyword">void</span> RBTNode<span class="token operator">::</span><span class="token function">setColor</span><span class="token punctuation">(</span>string color<span class="token punctuation">)</span> <span class="token punctuation">{</span>
    <span class="token keyword">this</span><span class="token operator">-</span><span class="token operator">></span>color <span class="token operator">=</span> color<span class="token punctuation">;</span>
<span class="token punctuation">}</span>
</code></pre>
<pre class=" language-cpp"><code class="language-cpp"><span class="token comment" spellcheck="true">//</span>
<span class="token comment" spellcheck="true">// Created by XQ on 2020/4/29.</span>
<span class="token comment" spellcheck="true">//</span>

<span class="token macro property">#<span class="token directive keyword">include</span> <span class="token string">"RBT.h"</span></span>


RBT<span class="token operator">::</span><span class="token function">RBT</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
    <span class="token keyword">this</span><span class="token operator">-</span><span class="token operator">></span>root <span class="token operator">=</span> <span class="token keyword">nullptr</span><span class="token punctuation">;</span>
<span class="token punctuation">}</span>

RBT<span class="token operator">::</span><span class="token function">RBT</span><span class="token punctuation">(</span>RBTNode <span class="token operator">*</span>node<span class="token punctuation">)</span> <span class="token punctuation">{</span>
    <span class="token keyword">this</span><span class="token operator">-</span><span class="token operator">></span>root <span class="token operator">=</span> node<span class="token punctuation">;</span>
<span class="token punctuation">}</span>

RBT<span class="token operator">::</span><span class="token operator">~</span><span class="token function">RBT</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
    cout <span class="token operator">&lt;&lt;</span> <span class="token string">"~RBT"</span> <span class="token operator">&lt;&lt;</span> endl<span class="token punctuation">;</span>
    <span class="token function">collectNode</span><span class="token punctuation">(</span><span class="token keyword">this</span><span class="token operator">-</span><span class="token operator">></span>root<span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token function">free</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>

<span class="token punctuation">}</span>

RBTNode <span class="token operator">*</span>RBT<span class="token operator">::</span><span class="token function">findSuccessor</span><span class="token punctuation">(</span>RBTNode <span class="token operator">*</span>node<span class="token punctuation">)</span> <span class="token punctuation">{</span>
    <span class="token keyword">if</span> <span class="token punctuation">(</span><span class="token operator">!</span>node<span class="token punctuation">)</span> <span class="token keyword">return</span> <span class="token keyword">nullptr</span><span class="token punctuation">;</span>
    <span class="token keyword">if</span> <span class="token punctuation">(</span>node<span class="token operator">-</span><span class="token operator">></span><span class="token function">getRight</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
        RBTNode <span class="token operator">*</span>p <span class="token operator">=</span> node<span class="token operator">-</span><span class="token operator">></span><span class="token function">getRight</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token keyword">while</span> <span class="token punctuation">(</span>p<span class="token operator">-</span><span class="token operator">></span><span class="token function">getLeft</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
            p <span class="token operator">=</span> p<span class="token operator">-</span><span class="token operator">></span><span class="token function">getLeft</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token punctuation">}</span>
        <span class="token keyword">return</span> p<span class="token punctuation">;</span>
    <span class="token punctuation">}</span> <span class="token keyword">else</span> <span class="token punctuation">{</span>
        RBTNode <span class="token operator">*</span>p <span class="token operator">=</span> node<span class="token operator">-</span><span class="token operator">></span><span class="token function">getParent</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
        RBTNode <span class="token operator">*</span>ch <span class="token operator">=</span> node<span class="token punctuation">;</span>
        <span class="token keyword">while</span> <span class="token punctuation">(</span>p <span class="token operator">&amp;&amp;</span> p<span class="token operator">-</span><span class="token operator">></span><span class="token function">getRight</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token operator">==</span> ch<span class="token punctuation">)</span> <span class="token punctuation">{</span>
            ch <span class="token operator">=</span> p<span class="token punctuation">;</span>
            p <span class="token operator">=</span> p<span class="token operator">-</span><span class="token operator">></span><span class="token function">getParent</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token punctuation">}</span>
        <span class="token keyword">return</span> p<span class="token punctuation">;</span>
    <span class="token punctuation">}</span>
<span class="token punctuation">}</span>

<span class="token keyword">void</span> RBT<span class="token operator">::</span><span class="token function">rotateLeft</span><span class="token punctuation">(</span>RBTNode <span class="token operator">*</span>node<span class="token punctuation">)</span> <span class="token punctuation">{</span>
    <span class="token keyword">if</span> <span class="token punctuation">(</span>node <span class="token operator">&amp;&amp;</span> node<span class="token operator">-</span><span class="token operator">></span><span class="token function">getRight</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
        RBTNode <span class="token operator">*</span>r <span class="token operator">=</span> node<span class="token operator">-</span><span class="token operator">></span><span class="token function">getRight</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token comment" spellcheck="true">// 1</span>
        node<span class="token operator">-</span><span class="token operator">></span><span class="token function">setRight</span><span class="token punctuation">(</span>r<span class="token operator">-</span><span class="token operator">></span><span class="token function">getLeft</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token comment" spellcheck="true">// 2</span>
        <span class="token keyword">if</span> <span class="token punctuation">(</span>r<span class="token operator">-</span><span class="token operator">></span><span class="token function">getLeft</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">)</span> r<span class="token operator">-</span><span class="token operator">></span><span class="token function">getLeft</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token operator">-</span><span class="token operator">></span><span class="token function">setParent</span><span class="token punctuation">(</span>node<span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token comment" spellcheck="true">// 3</span>
        r<span class="token operator">-</span><span class="token operator">></span><span class="token function">setParent</span><span class="token punctuation">(</span>node<span class="token operator">-</span><span class="token operator">></span><span class="token function">getParent</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token comment" spellcheck="true">// 4</span>
        <span class="token keyword">if</span> <span class="token punctuation">(</span><span class="token operator">!</span>node<span class="token operator">-</span><span class="token operator">></span><span class="token function">getParent</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">)</span> <span class="token keyword">this</span><span class="token operator">-</span><span class="token operator">></span>root <span class="token operator">=</span> r<span class="token punctuation">;</span>
        <span class="token keyword">else</span> <span class="token keyword">if</span> <span class="token punctuation">(</span>node<span class="token operator">-</span><span class="token operator">></span><span class="token function">getParent</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token operator">-</span><span class="token operator">></span><span class="token function">getLeft</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token operator">==</span> node<span class="token punctuation">)</span> <span class="token punctuation">{</span>
            node<span class="token operator">-</span><span class="token operator">></span><span class="token function">getParent</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token operator">-</span><span class="token operator">></span><span class="token function">setLeft</span><span class="token punctuation">(</span>r<span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token punctuation">}</span> <span class="token keyword">else</span> <span class="token keyword">if</span> <span class="token punctuation">(</span>node<span class="token operator">-</span><span class="token operator">></span><span class="token function">getParent</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token operator">-</span><span class="token operator">></span><span class="token function">getRight</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token operator">==</span> node<span class="token punctuation">)</span> <span class="token punctuation">{</span>
            node<span class="token operator">-</span><span class="token operator">></span><span class="token function">getParent</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token operator">-</span><span class="token operator">></span><span class="token function">setRight</span><span class="token punctuation">(</span>r<span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token punctuation">}</span>
        <span class="token comment" spellcheck="true">// 5</span>
        node<span class="token operator">-</span><span class="token operator">></span><span class="token function">setParent</span><span class="token punctuation">(</span>r<span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token comment" spellcheck="true">//6</span>
        r<span class="token operator">-</span><span class="token operator">></span><span class="token function">setLeft</span><span class="token punctuation">(</span>node<span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token punctuation">}</span>
<span class="token punctuation">}</span>

<span class="token keyword">void</span> RBT<span class="token operator">::</span><span class="token function">rotateRight</span><span class="token punctuation">(</span>RBTNode <span class="token operator">*</span>node<span class="token punctuation">)</span> <span class="token punctuation">{</span>
    <span class="token keyword">if</span> <span class="token punctuation">(</span>node <span class="token operator">&amp;&amp;</span> node<span class="token operator">-</span><span class="token operator">></span><span class="token function">getLeft</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
        RBTNode <span class="token operator">*</span>l <span class="token operator">=</span> node<span class="token operator">-</span><span class="token operator">></span><span class="token function">getLeft</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token comment" spellcheck="true">// 1</span>
        node<span class="token operator">-</span><span class="token operator">></span><span class="token function">setLeft</span><span class="token punctuation">(</span>l<span class="token operator">-</span><span class="token operator">></span><span class="token function">getRight</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token comment" spellcheck="true">// 2</span>
        <span class="token keyword">if</span> <span class="token punctuation">(</span>l<span class="token operator">-</span><span class="token operator">></span><span class="token function">getRight</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">)</span> l<span class="token operator">-</span><span class="token operator">></span><span class="token function">setParent</span><span class="token punctuation">(</span>node<span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token comment" spellcheck="true">// 3</span>
        l<span class="token operator">-</span><span class="token operator">></span><span class="token function">setParent</span><span class="token punctuation">(</span>node<span class="token operator">-</span><span class="token operator">></span><span class="token function">getParent</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token comment" spellcheck="true">// 4</span>
        <span class="token keyword">if</span> <span class="token punctuation">(</span><span class="token operator">!</span>node<span class="token operator">-</span><span class="token operator">></span><span class="token function">getParent</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">)</span> root <span class="token operator">=</span> l<span class="token punctuation">;</span>
        <span class="token keyword">else</span> <span class="token keyword">if</span> <span class="token punctuation">(</span>node<span class="token operator">-</span><span class="token operator">></span><span class="token function">getParent</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token operator">-</span><span class="token operator">></span><span class="token function">getLeft</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token operator">==</span> node<span class="token punctuation">)</span> <span class="token punctuation">{</span>
            node<span class="token operator">-</span><span class="token operator">></span><span class="token function">getParent</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token operator">-</span><span class="token operator">></span><span class="token function">setLeft</span><span class="token punctuation">(</span>l<span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token punctuation">}</span> <span class="token keyword">else</span> <span class="token keyword">if</span> <span class="token punctuation">(</span>node<span class="token operator">-</span><span class="token operator">></span><span class="token function">getParent</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token operator">-</span><span class="token operator">></span><span class="token function">getRight</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token operator">==</span> node<span class="token punctuation">)</span> <span class="token punctuation">{</span>
            node<span class="token operator">-</span><span class="token operator">></span><span class="token function">getParent</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token operator">-</span><span class="token operator">></span><span class="token function">setRight</span><span class="token punctuation">(</span>l<span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token punctuation">}</span>
        <span class="token comment" spellcheck="true">//5</span>
        node<span class="token operator">-</span><span class="token operator">></span><span class="token function">setParent</span><span class="token punctuation">(</span>l<span class="token punctuation">)</span><span class="token punctuation">;</span>
        l<span class="token operator">-</span><span class="token operator">></span><span class="token function">setRight</span><span class="token punctuation">(</span>node<span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token punctuation">}</span>
<span class="token punctuation">}</span>

<span class="token keyword">void</span> RBT<span class="token operator">::</span><span class="token function">fixAfterAdd</span><span class="token punctuation">(</span>RBTNode <span class="token operator">*</span>node<span class="token punctuation">)</span> <span class="token punctuation">{</span>
    node<span class="token operator">-</span><span class="token operator">></span><span class="token function">setColor</span><span class="token punctuation">(</span><span class="token string">"R"</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token keyword">while</span> <span class="token punctuation">(</span>node <span class="token operator">&amp;&amp;</span> node <span class="token operator">!=</span> <span class="token keyword">this</span><span class="token operator">-</span><span class="token operator">></span>root <span class="token operator">&amp;&amp;</span> node<span class="token operator">-</span><span class="token operator">></span><span class="token function">getParent</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token operator">-</span><span class="token operator">></span><span class="token function">getColor</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token operator">==</span> <span class="token string">"R"</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
        RBTNode <span class="token operator">*</span>father <span class="token operator">=</span> node<span class="token operator">-</span><span class="token operator">></span><span class="token function">getParent</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
        RBTNode <span class="token operator">*</span>grandfather <span class="token operator">=</span> father<span class="token operator">-</span><span class="token operator">></span><span class="token function">getParent</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>

        <span class="token keyword">if</span> <span class="token punctuation">(</span>father <span class="token operator">==</span> grandfather<span class="token operator">-</span><span class="token operator">></span><span class="token function">getLeft</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
            RBTNode <span class="token operator">*</span>uncle <span class="token operator">=</span> grandfather<span class="token operator">-</span><span class="token operator">></span><span class="token function">getRight</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>

            <span class="token keyword">if</span> <span class="token punctuation">(</span>uncle <span class="token operator">&amp;&amp;</span> uncle<span class="token operator">-</span><span class="token operator">></span><span class="token function">getColor</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token operator">==</span> <span class="token string">"R"</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
                father<span class="token operator">-</span><span class="token operator">></span><span class="token function">setColor</span><span class="token punctuation">(</span><span class="token string">"B"</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
                uncle<span class="token operator">-</span><span class="token operator">></span><span class="token function">setColor</span><span class="token punctuation">(</span><span class="token string">"B"</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
                grandfather<span class="token operator">-</span><span class="token operator">></span><span class="token function">setColor</span><span class="token punctuation">(</span><span class="token string">"R"</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
                node <span class="token operator">=</span> grandfather<span class="token punctuation">;</span>
            <span class="token punctuation">}</span> <span class="token keyword">else</span> <span class="token punctuation">{</span>
                <span class="token keyword">if</span> <span class="token punctuation">(</span>node <span class="token operator">==</span> father<span class="token operator">-</span><span class="token operator">></span><span class="token function">getRight</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
                    node <span class="token operator">=</span> father<span class="token punctuation">;</span>
                    <span class="token function">rotateLeft</span><span class="token punctuation">(</span>node<span class="token punctuation">)</span><span class="token punctuation">;</span>
                <span class="token punctuation">}</span>
                node<span class="token operator">-</span><span class="token operator">></span><span class="token function">getParent</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token operator">-</span><span class="token operator">></span><span class="token function">setColor</span><span class="token punctuation">(</span><span class="token string">"B"</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
                node<span class="token operator">-</span><span class="token operator">></span><span class="token function">getParent</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token operator">-</span><span class="token operator">></span><span class="token function">getParent</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token operator">-</span><span class="token operator">></span><span class="token function">setColor</span><span class="token punctuation">(</span><span class="token string">"R"</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
                <span class="token function">rotateRight</span><span class="token punctuation">(</span>node<span class="token operator">-</span><span class="token operator">></span><span class="token function">getParent</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token operator">-</span><span class="token operator">></span><span class="token function">getParent</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
            <span class="token punctuation">}</span>
        <span class="token punctuation">}</span> <span class="token keyword">else</span> <span class="token punctuation">{</span>
            RBTNode <span class="token operator">*</span>uncle <span class="token operator">=</span> grandfather<span class="token operator">-</span><span class="token operator">></span><span class="token function">getLeft</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>

            <span class="token keyword">if</span> <span class="token punctuation">(</span>uncle <span class="token operator">&amp;&amp;</span> uncle<span class="token operator">-</span><span class="token operator">></span><span class="token function">getColor</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token operator">==</span> <span class="token string">"R"</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
                father<span class="token operator">-</span><span class="token operator">></span><span class="token function">setColor</span><span class="token punctuation">(</span><span class="token string">"B"</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
                uncle<span class="token operator">-</span><span class="token operator">></span><span class="token function">setColor</span><span class="token punctuation">(</span><span class="token string">"B"</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
                grandfather<span class="token operator">-</span><span class="token operator">></span><span class="token function">setColor</span><span class="token punctuation">(</span><span class="token string">"R"</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
                node <span class="token operator">=</span> grandfather<span class="token punctuation">;</span>
            <span class="token punctuation">}</span> <span class="token keyword">else</span> <span class="token punctuation">{</span>
                <span class="token keyword">if</span> <span class="token punctuation">(</span>node <span class="token operator">==</span> father<span class="token operator">-</span><span class="token operator">></span><span class="token function">getLeft</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
                    node <span class="token operator">=</span> father<span class="token punctuation">;</span>
                    <span class="token function">rotateRight</span><span class="token punctuation">(</span>node<span class="token punctuation">)</span><span class="token punctuation">;</span>
                <span class="token punctuation">}</span>
                node<span class="token operator">-</span><span class="token operator">></span><span class="token function">getParent</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token operator">-</span><span class="token operator">></span><span class="token function">setColor</span><span class="token punctuation">(</span><span class="token string">"B"</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
                node<span class="token operator">-</span><span class="token operator">></span><span class="token function">getParent</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token operator">-</span><span class="token operator">></span><span class="token function">getParent</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token operator">-</span><span class="token operator">></span><span class="token function">setColor</span><span class="token punctuation">(</span><span class="token string">"R"</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
                <span class="token function">rotateLeft</span><span class="token punctuation">(</span>node<span class="token operator">-</span><span class="token operator">></span><span class="token function">getParent</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token operator">-</span><span class="token operator">></span><span class="token function">getParent</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
            <span class="token punctuation">}</span>
        <span class="token punctuation">}</span>
    <span class="token punctuation">}</span>
    <span class="token keyword">this</span><span class="token operator">-</span><span class="token operator">></span>root<span class="token operator">-</span><span class="token operator">></span><span class="token function">setColor</span><span class="token punctuation">(</span><span class="token string">"B"</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
<span class="token punctuation">}</span>

<span class="token keyword">void</span> RBT<span class="token operator">::</span><span class="token function">fixAfterErase</span><span class="token punctuation">(</span>RBTNode <span class="token operator">*</span>node<span class="token punctuation">)</span> <span class="token punctuation">{</span>
    RBTNode <span class="token operator">*</span> flag <span class="token operator">=</span> <span class="token keyword">nullptr</span><span class="token punctuation">;</span> <span class="token comment" spellcheck="true">// 由于node指向有变化 标记一下 调整好后删除</span>
    <span class="token keyword">while</span> <span class="token punctuation">(</span>node <span class="token operator">!=</span> <span class="token keyword">this</span><span class="token operator">-</span><span class="token operator">></span>root <span class="token operator">&amp;&amp;</span> node<span class="token operator">-</span><span class="token operator">></span><span class="token function">getColor</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token operator">==</span> <span class="token string">"B"</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token keyword">if</span> <span class="token punctuation">(</span>node <span class="token operator">==</span> node<span class="token operator">-</span><span class="token operator">></span><span class="token function">getParent</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token operator">-</span><span class="token operator">></span><span class="token function">getLeft</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
            RBTNode <span class="token operator">*</span>sib <span class="token operator">=</span> node<span class="token operator">-</span><span class="token operator">></span><span class="token function">getParent</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token operator">-</span><span class="token operator">></span><span class="token function">getRight</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
            <span class="token keyword">if</span> <span class="token punctuation">(</span>sib<span class="token operator">-</span><span class="token operator">></span><span class="token function">getColor</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token operator">==</span> <span class="token string">"R"</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
                sib<span class="token operator">-</span><span class="token operator">></span><span class="token function">setColor</span><span class="token punctuation">(</span><span class="token string">"B"</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
                node<span class="token operator">-</span><span class="token operator">></span><span class="token function">getParent</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token operator">-</span><span class="token operator">></span><span class="token function">setColor</span><span class="token punctuation">(</span><span class="token string">"R"</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
                <span class="token function">rotateLeft</span><span class="token punctuation">(</span>node<span class="token operator">-</span><span class="token operator">></span><span class="token function">getParent</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
                sib <span class="token operator">=</span> node<span class="token operator">-</span><span class="token operator">></span><span class="token function">getParent</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token operator">-</span><span class="token operator">></span><span class="token function">getRight</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
            <span class="token punctuation">}</span>
            <span class="token keyword">if</span> <span class="token punctuation">(</span><span class="token operator">!</span>sib<span class="token operator">-</span><span class="token operator">></span><span class="token function">getLeft</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token operator">&amp;&amp;</span> <span class="token operator">!</span>sib<span class="token operator">-</span><span class="token operator">></span><span class="token function">getRight</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
                sib<span class="token operator">-</span><span class="token operator">></span><span class="token function">setColor</span><span class="token punctuation">(</span><span class="token string">"R"</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
                node <span class="token operator">=</span> node<span class="token operator">-</span><span class="token operator">></span><span class="token function">getParent</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
                <span class="token keyword">if</span><span class="token punctuation">(</span><span class="token operator">!</span>flag<span class="token punctuation">)</span> flag <span class="token operator">=</span> node<span class="token punctuation">;</span>
            <span class="token punctuation">}</span> <span class="token keyword">else</span> <span class="token keyword">if</span> <span class="token punctuation">(</span>sib<span class="token operator">-</span><span class="token operator">></span><span class="token function">getLeft</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token operator">&amp;&amp;</span> sib<span class="token operator">-</span><span class="token operator">></span><span class="token function">getLeft</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token operator">-</span><span class="token operator">></span><span class="token function">getColor</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token operator">==</span> <span class="token string">"B"</span> <span class="token operator">&amp;&amp;</span>
                       sib<span class="token operator">-</span><span class="token operator">></span><span class="token function">getRight</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token operator">&amp;&amp;</span> sib<span class="token operator">-</span><span class="token operator">></span><span class="token function">getRight</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token operator">-</span><span class="token operator">></span><span class="token function">getColor</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token operator">==</span> <span class="token string">"B"</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
                <span class="token comment" spellcheck="true">// 兄弟都为黑节点，需要找父母帮忙</span>
                sib<span class="token operator">-</span><span class="token operator">></span><span class="token function">setColor</span><span class="token punctuation">(</span><span class="token string">"R"</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
                node <span class="token operator">=</span> node<span class="token operator">-</span><span class="token operator">></span><span class="token function">getParent</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
            <span class="token punctuation">}</span> <span class="token keyword">else</span> <span class="token punctuation">{</span>
                <span class="token keyword">if</span> <span class="token punctuation">(</span><span class="token operator">!</span>sib<span class="token operator">-</span><span class="token operator">></span><span class="token function">getRight</span><span class="token punctuation">(</span><span class="token punctuation">)</span>  <span class="token operator">||</span> sib<span class="token operator">-</span><span class="token operator">></span><span class="token function">getRight</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token operator">-</span><span class="token operator">></span><span class="token function">getColor</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token operator">==</span> <span class="token string">"B"</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
                    sib<span class="token operator">-</span><span class="token operator">></span><span class="token function">setColor</span><span class="token punctuation">(</span><span class="token string">"R"</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
                    sib<span class="token operator">-</span><span class="token operator">></span><span class="token function">getLeft</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token operator">-</span><span class="token operator">></span><span class="token function">setColor</span><span class="token punctuation">(</span><span class="token string">"B"</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
                    <span class="token function">rotateRight</span><span class="token punctuation">(</span>sib<span class="token punctuation">)</span><span class="token punctuation">;</span>
                    sib <span class="token operator">=</span> node<span class="token operator">-</span><span class="token operator">></span><span class="token function">getParent</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token operator">-</span><span class="token operator">></span><span class="token function">getRight</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
                <span class="token punctuation">}</span>
                sib<span class="token operator">-</span><span class="token operator">></span><span class="token function">setColor</span><span class="token punctuation">(</span>node<span class="token operator">-</span><span class="token operator">></span><span class="token function">getParent</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token operator">-</span><span class="token operator">></span><span class="token function">getColor</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
                node<span class="token operator">-</span><span class="token operator">></span><span class="token function">getParent</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token operator">-</span><span class="token operator">></span><span class="token function">setColor</span><span class="token punctuation">(</span><span class="token string">"B"</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
                sib<span class="token operator">-</span><span class="token operator">></span><span class="token function">getRight</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token operator">-</span><span class="token operator">></span><span class="token function">setColor</span><span class="token punctuation">(</span><span class="token string">"B"</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
                <span class="token function">rotateLeft</span><span class="token punctuation">(</span>node<span class="token operator">-</span><span class="token operator">></span><span class="token function">getParent</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
                node <span class="token operator">=</span> root<span class="token punctuation">;</span>
            <span class="token punctuation">}</span>
        <span class="token punctuation">}</span> <span class="token keyword">else</span> <span class="token punctuation">{</span>
            RBTNode <span class="token operator">*</span>sib <span class="token operator">=</span> node<span class="token operator">-</span><span class="token operator">></span><span class="token function">getParent</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token operator">-</span><span class="token operator">></span><span class="token function">getLeft</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
            <span class="token keyword">if</span> <span class="token punctuation">(</span>sib<span class="token operator">-</span><span class="token operator">></span><span class="token function">getColor</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token operator">==</span> <span class="token string">"R"</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
                sib<span class="token operator">-</span><span class="token operator">></span><span class="token function">setColor</span><span class="token punctuation">(</span><span class="token string">"B"</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
                node<span class="token operator">-</span><span class="token operator">></span><span class="token function">getParent</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token operator">-</span><span class="token operator">></span><span class="token function">setColor</span><span class="token punctuation">(</span><span class="token string">"R"</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
                <span class="token function">rotateRight</span><span class="token punctuation">(</span>node<span class="token operator">-</span><span class="token operator">></span><span class="token function">getParent</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
                sib <span class="token operator">=</span> node<span class="token operator">-</span><span class="token operator">></span><span class="token function">getParent</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token operator">-</span><span class="token operator">></span><span class="token function">getLeft</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
            <span class="token punctuation">}</span>

            <span class="token keyword">if</span> <span class="token punctuation">(</span><span class="token operator">!</span>sib<span class="token operator">-</span><span class="token operator">></span><span class="token function">getLeft</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token operator">&amp;&amp;</span> <span class="token operator">!</span>sib<span class="token operator">-</span><span class="token operator">></span><span class="token function">getRight</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
                sib<span class="token operator">-</span><span class="token operator">></span><span class="token function">setColor</span><span class="token punctuation">(</span><span class="token string">"R"</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
                node <span class="token operator">=</span> node<span class="token operator">-</span><span class="token operator">></span><span class="token function">getParent</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
                <span class="token keyword">if</span><span class="token punctuation">(</span><span class="token operator">!</span>flag<span class="token punctuation">)</span> flag <span class="token operator">=</span> node<span class="token punctuation">;</span>
            <span class="token punctuation">}</span> <span class="token keyword">else</span> <span class="token keyword">if</span> <span class="token punctuation">(</span>sib<span class="token operator">-</span><span class="token operator">></span><span class="token function">getLeft</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token operator">&amp;&amp;</span> sib<span class="token operator">-</span><span class="token operator">></span><span class="token function">getLeft</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token operator">-</span><span class="token operator">></span><span class="token function">getColor</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token operator">==</span> <span class="token string">"B"</span> <span class="token operator">&amp;&amp;</span>
                    sib<span class="token operator">-</span><span class="token operator">></span><span class="token function">getRight</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token operator">&amp;&amp;</span> sib<span class="token operator">-</span><span class="token operator">></span><span class="token function">getRight</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token operator">-</span><span class="token operator">></span><span class="token function">getColor</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token operator">==</span> <span class="token string">"B"</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
                <span class="token comment" spellcheck="true">// 兄弟都为黑节点，需要找父母帮忙</span>
                sib<span class="token operator">-</span><span class="token operator">></span><span class="token function">setColor</span><span class="token punctuation">(</span><span class="token string">"R"</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
                node <span class="token operator">=</span> node<span class="token operator">-</span><span class="token operator">></span><span class="token function">getParent</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
            <span class="token punctuation">}</span> <span class="token keyword">else</span> <span class="token punctuation">{</span>
                <span class="token keyword">if</span> <span class="token punctuation">(</span><span class="token operator">!</span>sib<span class="token operator">-</span><span class="token operator">></span><span class="token function">getLeft</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token operator">||</span> sib<span class="token operator">-</span><span class="token operator">></span><span class="token function">getLeft</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token operator">-</span><span class="token operator">></span><span class="token function">getColor</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token operator">==</span> <span class="token string">"B"</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
                    sib<span class="token operator">-</span><span class="token operator">></span><span class="token function">setColor</span><span class="token punctuation">(</span><span class="token string">"R"</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
                    sib<span class="token operator">-</span><span class="token operator">></span><span class="token function">getRight</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token operator">-</span><span class="token operator">></span><span class="token function">setColor</span><span class="token punctuation">(</span><span class="token string">"B"</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
                    <span class="token function">rotateLeft</span><span class="token punctuation">(</span>sib<span class="token punctuation">)</span><span class="token punctuation">;</span>
                    sib <span class="token operator">=</span> node<span class="token operator">-</span><span class="token operator">></span><span class="token function">getParent</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token operator">-</span><span class="token operator">></span><span class="token function">getLeft</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
                <span class="token punctuation">}</span>
                sib<span class="token operator">-</span><span class="token operator">></span><span class="token function">setColor</span><span class="token punctuation">(</span>node<span class="token operator">-</span><span class="token operator">></span><span class="token function">getParent</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token operator">-</span><span class="token operator">></span><span class="token function">getColor</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
                node<span class="token operator">-</span><span class="token operator">></span><span class="token function">getParent</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token operator">-</span><span class="token operator">></span><span class="token function">setColor</span><span class="token punctuation">(</span><span class="token string">"B"</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
                sib<span class="token operator">-</span><span class="token operator">></span><span class="token function">getLeft</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token operator">-</span><span class="token operator">></span><span class="token function">setColor</span><span class="token punctuation">(</span><span class="token string">"B"</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
                <span class="token function">rotateRight</span><span class="token punctuation">(</span>node<span class="token operator">-</span><span class="token operator">></span><span class="token function">getParent</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
                node <span class="token operator">=</span> root<span class="token punctuation">;</span>
            <span class="token punctuation">}</span>
        <span class="token punctuation">}</span>
    <span class="token punctuation">}</span>
    <span class="token keyword">if</span><span class="token punctuation">(</span>flag<span class="token punctuation">)</span> node <span class="token operator">=</span> flag<span class="token punctuation">;</span>
    node<span class="token operator">-</span><span class="token operator">></span><span class="token function">setColor</span><span class="token punctuation">(</span><span class="token string">"B"</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
<span class="token punctuation">}</span>

RBTNode <span class="token operator">*</span>RBT<span class="token operator">::</span><span class="token function">getRoot</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
    <span class="token keyword">return</span> <span class="token keyword">this</span><span class="token operator">-</span><span class="token operator">></span>root<span class="token punctuation">;</span>
<span class="token punctuation">}</span>

RBTNode <span class="token operator">*</span>RBT<span class="token operator">::</span><span class="token function">get</span><span class="token punctuation">(</span><span class="token keyword">int</span> value<span class="token punctuation">)</span> <span class="token punctuation">{</span>
    RBTNode <span class="token operator">*</span>p <span class="token operator">=</span> <span class="token keyword">this</span><span class="token operator">-</span><span class="token operator">></span>root<span class="token punctuation">;</span>
    <span class="token keyword">while</span> <span class="token punctuation">(</span>p<span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token keyword">if</span> <span class="token punctuation">(</span>p<span class="token operator">-</span><span class="token operator">></span><span class="token function">getValue</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token operator">==</span> value<span class="token punctuation">)</span> <span class="token keyword">return</span> p<span class="token punctuation">;</span>
        <span class="token keyword">else</span> <span class="token keyword">if</span> <span class="token punctuation">(</span>p<span class="token operator">-</span><span class="token operator">></span><span class="token function">getValue</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token operator">></span> value<span class="token punctuation">)</span> p <span class="token operator">=</span> p<span class="token operator">-</span><span class="token operator">></span><span class="token function">getLeft</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token keyword">else</span> p <span class="token operator">=</span> p<span class="token operator">-</span><span class="token operator">></span><span class="token function">getRight</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token punctuation">}</span>
    <span class="token keyword">return</span> <span class="token keyword">nullptr</span><span class="token punctuation">;</span>
<span class="token punctuation">}</span>

<span class="token keyword">void</span> RBT<span class="token operator">::</span><span class="token function">add</span><span class="token punctuation">(</span>RBTNode <span class="token operator">*</span>node<span class="token punctuation">)</span> <span class="token punctuation">{</span>
    RBTNode <span class="token operator">*</span>p <span class="token operator">=</span> <span class="token keyword">this</span><span class="token operator">-</span><span class="token operator">></span>root<span class="token punctuation">;</span>
    <span class="token keyword">if</span> <span class="token punctuation">(</span><span class="token operator">!</span>p<span class="token punctuation">)</span> <span class="token punctuation">{</span>
        node<span class="token operator">-</span><span class="token operator">></span><span class="token function">setColor</span><span class="token punctuation">(</span><span class="token string">"B"</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token keyword">this</span><span class="token operator">-</span><span class="token operator">></span>root <span class="token operator">=</span> node<span class="token punctuation">;</span>
        <span class="token keyword">return</span><span class="token punctuation">;</span>
    <span class="token punctuation">}</span>
    <span class="token keyword">while</span> <span class="token punctuation">(</span>p<span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token keyword">if</span> <span class="token punctuation">(</span>p<span class="token operator">-</span><span class="token operator">></span><span class="token function">getValue</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token operator">==</span> node<span class="token operator">-</span><span class="token operator">></span><span class="token function">getValue</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">)</span> <span class="token keyword">return</span><span class="token punctuation">;</span>
        <span class="token keyword">else</span> <span class="token keyword">if</span> <span class="token punctuation">(</span>p<span class="token operator">-</span><span class="token operator">></span><span class="token function">getValue</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token operator">></span> node<span class="token operator">-</span><span class="token operator">></span><span class="token function">getValue</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
            <span class="token comment" spellcheck="true">// go left</span>
            <span class="token keyword">if</span> <span class="token punctuation">(</span>p<span class="token operator">-</span><span class="token operator">></span><span class="token function">getLeft</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">)</span> p <span class="token operator">=</span> p<span class="token operator">-</span><span class="token operator">></span><span class="token function">getLeft</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
            <span class="token keyword">else</span> <span class="token punctuation">{</span>
                node<span class="token operator">-</span><span class="token operator">></span><span class="token function">setParent</span><span class="token punctuation">(</span>p<span class="token punctuation">)</span><span class="token punctuation">;</span>
                p<span class="token operator">-</span><span class="token operator">></span><span class="token function">setLeft</span><span class="token punctuation">(</span>node<span class="token punctuation">)</span><span class="token punctuation">;</span>
                <span class="token keyword">break</span><span class="token punctuation">;</span>
            <span class="token punctuation">}</span>
        <span class="token punctuation">}</span> <span class="token keyword">else</span> <span class="token punctuation">{</span>
            <span class="token comment" spellcheck="true">// go right</span>
            <span class="token keyword">if</span> <span class="token punctuation">(</span>p<span class="token operator">-</span><span class="token operator">></span><span class="token function">getRight</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">)</span> p <span class="token operator">=</span> p<span class="token operator">-</span><span class="token operator">></span><span class="token function">getRight</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
            <span class="token keyword">else</span> <span class="token punctuation">{</span>
                node<span class="token operator">-</span><span class="token operator">></span><span class="token function">setParent</span><span class="token punctuation">(</span>p<span class="token punctuation">)</span><span class="token punctuation">;</span>
                p<span class="token operator">-</span><span class="token operator">></span><span class="token function">setRight</span><span class="token punctuation">(</span>node<span class="token punctuation">)</span><span class="token punctuation">;</span>
                <span class="token keyword">break</span><span class="token punctuation">;</span>
            <span class="token punctuation">}</span>
        <span class="token punctuation">}</span>
    <span class="token punctuation">}</span>
    <span class="token function">fixAfterAdd</span><span class="token punctuation">(</span>node<span class="token punctuation">)</span><span class="token punctuation">;</span>
<span class="token punctuation">}</span>

<span class="token keyword">void</span> RBT<span class="token operator">::</span><span class="token function">erase</span><span class="token punctuation">(</span>RBTNode <span class="token operator">*</span>node<span class="token punctuation">)</span> <span class="token punctuation">{</span>
    <span class="token keyword">if</span> <span class="token punctuation">(</span><span class="token operator">!</span>node<span class="token punctuation">)</span> <span class="token keyword">return</span><span class="token punctuation">;</span>
    <span class="token keyword">if</span> <span class="token punctuation">(</span>node<span class="token operator">-</span><span class="token operator">></span><span class="token function">getLeft</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token operator">&amp;&amp;</span> node<span class="token operator">-</span><span class="token operator">></span><span class="token function">getRight</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token comment" spellcheck="true">// 查找后继节点</span>
        RBTNode <span class="token operator">*</span>s <span class="token operator">=</span> <span class="token function">findSuccessor</span><span class="token punctuation">(</span>node<span class="token punctuation">)</span><span class="token punctuation">;</span>
        node<span class="token operator">-</span><span class="token operator">></span><span class="token function">setValue</span><span class="token punctuation">(</span>s<span class="token operator">-</span><span class="token operator">></span><span class="token function">getValue</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
        node <span class="token operator">=</span> s<span class="token punctuation">;</span>
    <span class="token punctuation">}</span>
    <span class="token comment" spellcheck="true">// 此时如果找到后继节点，则node一定不会有两棵子树 即没有左子树</span>
    RBTNode <span class="token operator">*</span>replace <span class="token operator">=</span> node<span class="token operator">-</span><span class="token operator">></span><span class="token function">getLeft</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token operator">?</span> node<span class="token operator">-</span><span class="token operator">></span><span class="token function">getLeft</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token operator">:</span> node<span class="token operator">-</span><span class="token operator">></span><span class="token function">getRight</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token keyword">if</span> <span class="token punctuation">(</span>replace<span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token comment" spellcheck="true">// 存在一颗子树</span>
        replace<span class="token operator">-</span><span class="token operator">></span><span class="token function">setParent</span><span class="token punctuation">(</span>node<span class="token operator">-</span><span class="token operator">></span><span class="token function">getParent</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token keyword">if</span> <span class="token punctuation">(</span><span class="token operator">!</span>node<span class="token operator">-</span><span class="token operator">></span><span class="token function">getParent</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
            <span class="token keyword">this</span><span class="token operator">-</span><span class="token operator">></span>root <span class="token operator">=</span> replace<span class="token punctuation">;</span>
        <span class="token punctuation">}</span> <span class="token keyword">else</span> <span class="token keyword">if</span> <span class="token punctuation">(</span>node<span class="token operator">-</span><span class="token operator">></span><span class="token function">getParent</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token operator">-</span><span class="token operator">></span><span class="token function">getLeft</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token operator">==</span> node<span class="token punctuation">)</span> <span class="token punctuation">{</span>
            node<span class="token operator">-</span><span class="token operator">></span><span class="token function">getParent</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token operator">-</span><span class="token operator">></span><span class="token function">setLeft</span><span class="token punctuation">(</span>replace<span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token punctuation">}</span> <span class="token keyword">else</span> <span class="token keyword">if</span> <span class="token punctuation">(</span>node<span class="token operator">-</span><span class="token operator">></span><span class="token function">getParent</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token operator">-</span><span class="token operator">></span><span class="token function">getRight</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token operator">==</span> node<span class="token punctuation">)</span> <span class="token punctuation">{</span>
            node<span class="token operator">-</span><span class="token operator">></span><span class="token function">getParent</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token operator">-</span><span class="token operator">></span><span class="token function">setRight</span><span class="token punctuation">(</span>replace<span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token punctuation">}</span>
        node<span class="token operator">-</span><span class="token operator">></span><span class="token function">setLeft</span><span class="token punctuation">(</span><span class="token keyword">nullptr</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
        node<span class="token operator">-</span><span class="token operator">></span><span class="token function">setRight</span><span class="token punctuation">(</span><span class="token keyword">nullptr</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
        node<span class="token operator">-</span><span class="token operator">></span><span class="token function">setParent</span><span class="token punctuation">(</span><span class="token keyword">nullptr</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token keyword">if</span> <span class="token punctuation">(</span>node<span class="token operator">-</span><span class="token operator">></span><span class="token function">getColor</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token operator">==</span> <span class="token string">"B"</span><span class="token punctuation">)</span> <span class="token function">fixAfterErase</span><span class="token punctuation">(</span>replace<span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token keyword">delete</span> node<span class="token punctuation">;</span>
    <span class="token punctuation">}</span> <span class="token keyword">else</span> <span class="token keyword">if</span> <span class="token punctuation">(</span><span class="token operator">!</span>node<span class="token operator">-</span><span class="token operator">></span><span class="token function">getParent</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token keyword">this</span><span class="token operator">-</span><span class="token operator">></span>root <span class="token operator">=</span> <span class="token keyword">nullptr</span><span class="token punctuation">;</span>
    <span class="token punctuation">}</span> <span class="token keyword">else</span> <span class="token punctuation">{</span>
        <span class="token comment" spellcheck="true">// 不存在子树</span>
        <span class="token keyword">if</span> <span class="token punctuation">(</span>node<span class="token operator">-</span><span class="token operator">></span><span class="token function">getColor</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token operator">==</span> <span class="token string">"B"</span><span class="token punctuation">)</span> <span class="token function">fixAfterErase</span><span class="token punctuation">(</span>node<span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token keyword">if</span> <span class="token punctuation">(</span>node<span class="token operator">-</span><span class="token operator">></span><span class="token function">getParent</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
            <span class="token keyword">if</span> <span class="token punctuation">(</span>node<span class="token operator">-</span><span class="token operator">></span><span class="token function">getParent</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token operator">-</span><span class="token operator">></span><span class="token function">getLeft</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token operator">==</span> node<span class="token punctuation">)</span> <span class="token punctuation">{</span>
                node<span class="token operator">-</span><span class="token operator">></span><span class="token function">getParent</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token operator">-</span><span class="token operator">></span><span class="token function">setLeft</span><span class="token punctuation">(</span><span class="token keyword">nullptr</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
            <span class="token punctuation">}</span> <span class="token keyword">else</span> <span class="token keyword">if</span> <span class="token punctuation">(</span>node<span class="token operator">-</span><span class="token operator">></span><span class="token function">getParent</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token operator">-</span><span class="token operator">></span><span class="token function">getRight</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token operator">==</span> node<span class="token punctuation">)</span> <span class="token punctuation">{</span>
                node<span class="token operator">-</span><span class="token operator">></span><span class="token function">getParent</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token operator">-</span><span class="token operator">></span><span class="token function">setRight</span><span class="token punctuation">(</span><span class="token keyword">nullptr</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
            <span class="token punctuation">}</span>
            node<span class="token operator">-</span><span class="token operator">></span><span class="token function">setParent</span><span class="token punctuation">(</span><span class="token keyword">nullptr</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
            <span class="token keyword">delete</span> node<span class="token punctuation">;</span>
        <span class="token punctuation">}</span>
    <span class="token punctuation">}</span>
<span class="token punctuation">}</span>

<span class="token keyword">void</span> RBT<span class="token operator">::</span><span class="token function">printNULL</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
    cout <span class="token operator">&lt;&lt;</span> <span class="token string">"[null]"</span><span class="token punctuation">;</span>
<span class="token punctuation">}</span>

<span class="token keyword">void</span> RBT<span class="token operator">::</span><span class="token function">print</span><span class="token punctuation">(</span>RBTNode <span class="token operator">*</span>node<span class="token punctuation">)</span> <span class="token punctuation">{</span>
    cout <span class="token operator">&lt;&lt;</span> <span class="token string">'['</span> <span class="token operator">&lt;&lt;</span> node<span class="token operator">-</span><span class="token operator">></span><span class="token function">getValue</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token operator">&lt;&lt;</span> <span class="token string">','</span> <span class="token operator">&lt;&lt;</span> node<span class="token operator">-</span><span class="token operator">></span><span class="token function">getColor</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token operator">&lt;&lt;</span> <span class="token string">']'</span><span class="token punctuation">;</span>
<span class="token punctuation">}</span>

<span class="token keyword">void</span> RBT<span class="token operator">::</span><span class="token function">preOrder</span><span class="token punctuation">(</span>RBTNode <span class="token operator">*</span>node<span class="token punctuation">)</span> <span class="token punctuation">{</span>
    <span class="token keyword">if</span> <span class="token punctuation">(</span><span class="token operator">!</span>node<span class="token punctuation">)</span> <span class="token punctuation">{</span>
<span class="token comment" spellcheck="true">//        printNULL();</span>
        <span class="token keyword">return</span><span class="token punctuation">;</span>
    <span class="token punctuation">}</span>
    <span class="token function">print</span><span class="token punctuation">(</span>node<span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token function">preOrder</span><span class="token punctuation">(</span>node<span class="token operator">-</span><span class="token operator">></span><span class="token function">getLeft</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token function">preOrder</span><span class="token punctuation">(</span>node<span class="token operator">-</span><span class="token operator">></span><span class="token function">getRight</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">;</span>

<span class="token punctuation">}</span>

<span class="token keyword">void</span> RBT<span class="token operator">::</span><span class="token function">inOrder</span><span class="token punctuation">(</span>RBTNode <span class="token operator">*</span>node<span class="token punctuation">)</span> <span class="token punctuation">{</span>
    <span class="token keyword">if</span> <span class="token punctuation">(</span><span class="token operator">!</span>node<span class="token punctuation">)</span> <span class="token punctuation">{</span>
<span class="token comment" spellcheck="true">//        printNULL();</span>
        <span class="token keyword">return</span><span class="token punctuation">;</span>
    <span class="token punctuation">}</span>
    <span class="token function">inOrder</span><span class="token punctuation">(</span>node<span class="token operator">-</span><span class="token operator">></span><span class="token function">getLeft</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token function">print</span><span class="token punctuation">(</span>node<span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token function">inOrder</span><span class="token punctuation">(</span>node<span class="token operator">-</span><span class="token operator">></span><span class="token function">getRight</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
<span class="token punctuation">}</span>

<span class="token keyword">void</span> RBT<span class="token operator">::</span><span class="token function">postOrder</span><span class="token punctuation">(</span>RBTNode <span class="token operator">*</span>node<span class="token punctuation">)</span> <span class="token punctuation">{</span>
    <span class="token keyword">if</span> <span class="token punctuation">(</span><span class="token operator">!</span>node<span class="token punctuation">)</span> <span class="token punctuation">{</span>
<span class="token comment" spellcheck="true">//        printNULL();</span>
        <span class="token keyword">return</span><span class="token punctuation">;</span>
    <span class="token punctuation">}</span>
    <span class="token function">postOrder</span><span class="token punctuation">(</span>node<span class="token operator">-</span><span class="token operator">></span><span class="token function">getLeft</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token function">postOrder</span><span class="token punctuation">(</span>node<span class="token operator">-</span><span class="token operator">></span><span class="token function">getRight</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token function">print</span><span class="token punctuation">(</span>node<span class="token punctuation">)</span><span class="token punctuation">;</span>
<span class="token punctuation">}</span>

<span class="token keyword">void</span> RBT<span class="token operator">::</span><span class="token function">levelOrder</span><span class="token punctuation">(</span>RBTNode <span class="token operator">*</span>node<span class="token punctuation">)</span> <span class="token punctuation">{</span>
    queue<span class="token operator">&lt;</span>RBTNode <span class="token operator">*</span><span class="token operator">></span> q<span class="token punctuation">;</span>
    <span class="token keyword">if</span> <span class="token punctuation">(</span><span class="token operator">!</span>node<span class="token punctuation">)</span> <span class="token punctuation">{</span>
<span class="token comment" spellcheck="true">//        printNULL();</span>
        <span class="token keyword">return</span><span class="token punctuation">;</span>
    <span class="token punctuation">}</span>
    q<span class="token punctuation">.</span><span class="token function">push</span><span class="token punctuation">(</span>node<span class="token punctuation">)</span><span class="token punctuation">;</span>
    RBTNode <span class="token operator">*</span>back <span class="token operator">=</span> q<span class="token punctuation">.</span><span class="token function">back</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token keyword">while</span> <span class="token punctuation">(</span><span class="token operator">!</span>q<span class="token punctuation">.</span><span class="token function">empty</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
        RBTNode <span class="token operator">*</span>p <span class="token operator">=</span> q<span class="token punctuation">.</span><span class="token function">front</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
        q<span class="token punctuation">.</span><span class="token function">pop</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token function">print</span><span class="token punctuation">(</span>p<span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token keyword">if</span> <span class="token punctuation">(</span>p<span class="token operator">-</span><span class="token operator">></span><span class="token function">getLeft</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">)</span> q<span class="token punctuation">.</span><span class="token function">push</span><span class="token punctuation">(</span>p<span class="token operator">-</span><span class="token operator">></span><span class="token function">getLeft</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token keyword">if</span> <span class="token punctuation">(</span>p<span class="token operator">-</span><span class="token operator">></span><span class="token function">getRight</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">)</span> q<span class="token punctuation">.</span><span class="token function">push</span><span class="token punctuation">(</span>p<span class="token operator">-</span><span class="token operator">></span><span class="token function">getRight</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token keyword">if</span> <span class="token punctuation">(</span>back <span class="token operator">==</span> p<span class="token punctuation">)</span> <span class="token punctuation">{</span>
            cout <span class="token operator">&lt;&lt;</span> endl<span class="token punctuation">;</span>
            back <span class="token operator">=</span> q<span class="token punctuation">.</span><span class="token function">back</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token punctuation">}</span>
    <span class="token punctuation">}</span>
<span class="token punctuation">}</span>

<span class="token keyword">void</span> RBT<span class="token operator">::</span><span class="token function">collectNode</span><span class="token punctuation">(</span>RBTNode <span class="token operator">*</span>node<span class="token punctuation">)</span> <span class="token punctuation">{</span>
    <span class="token keyword">if</span> <span class="token punctuation">(</span><span class="token operator">!</span>node<span class="token punctuation">)</span> <span class="token keyword">return</span><span class="token punctuation">;</span>

    <span class="token keyword">this</span><span class="token operator">-</span><span class="token operator">></span>nodePool<span class="token punctuation">.</span><span class="token function">push_back</span><span class="token punctuation">(</span>node<span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token keyword">if</span> <span class="token punctuation">(</span>node<span class="token operator">-</span><span class="token operator">></span><span class="token function">getLeft</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token function">collectNode</span><span class="token punctuation">(</span>node<span class="token operator">-</span><span class="token operator">></span><span class="token function">getLeft</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token punctuation">}</span>
    <span class="token keyword">if</span> <span class="token punctuation">(</span>node<span class="token operator">-</span><span class="token operator">></span><span class="token function">getRight</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token function">collectNode</span><span class="token punctuation">(</span>node<span class="token operator">-</span><span class="token operator">></span><span class="token function">getRight</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token punctuation">}</span>


<span class="token punctuation">}</span>

<span class="token keyword">void</span> RBT<span class="token operator">::</span><span class="token function">free</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
    <span class="token keyword">for</span><span class="token punctuation">(</span>RBTNode<span class="token operator">*</span> item<span class="token operator">:</span> <span class="token keyword">this</span><span class="token operator">-</span><span class="token operator">></span>nodePool<span class="token punctuation">)</span> <span class="token punctuation">{</span>
        cout <span class="token operator">&lt;&lt;</span> <span class="token string">"del:"</span> <span class="token operator">&lt;&lt;</span> item<span class="token operator">-</span><span class="token operator">></span><span class="token function">getValue</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token operator">&lt;&lt;</span> endl<span class="token punctuation">;</span>
        <span class="token keyword">delete</span> item<span class="token punctuation">;</span>
    <span class="token punctuation">}</span>
<span class="token punctuation">}</span>
</code></pre>

    </article>
    <!-- license  -->
    
        <div class="license-wrapper">
            <p>原文作者：<a href="https://blog.xq99.org">XQ</a>
            <p>原文链接：<a href="https://blog.xq99.org/posts/6.红黑树的实现/">https://blog.xq99.org/posts/6.红黑树的实现/</a>
            <p>发表日期：<a href="https://blog.xq99.org/posts/6.红黑树的实现/">December 3rd 2020, 2:32:42 pm</a>
            <p>更新日期：<a href="https://blog.xq99.org/posts/6.红黑树的实现/">December 3rd 2020, 2:32:45 pm</a>
            <p>版权声明：本文采用<a rel="license" href="http://creativecommons.org/licenses/by-nc/4.0/">知识共享署名-非商业性使用 4.0 国际许可协议</a>进行许可</p>
        </div>
    
    <!-- paginator  -->
    <ul class="post-paginator">
        <li class="next">
            
                <div class="nextSlogan">Next Post</div>
                <a href= "/posts/7.收藏夹/" title= "收藏夹">
                    <div class="nextTitle">收藏夹</div>
                </a>
            
        </li>
        <li class="previous">
            
                <div class="prevSlogan">Previous Post</div>
                <a href= "/posts/5.Git命令/" title= "Git命令">
                    <div class="prevTitle">Git命令</div>
                </a>
            
        </li>
    </ul>
    <!-- 评论插件 -->
    <!-- 来必力City版安装代码 -->

<!-- City版安装代码已完成 -->
    
    <div id="disqus_thread"></div>
    <script>
        /**
    *  RECOMMENDED CONFIGURATION VARIABLES: EDIT AND UNCOMMENT THE SECTION BELOW TO INSERT DYNAMIC VALUES FROM YOUR PLATFORM OR CMS.
    *  LEARN WHY DEFINING THESE VARIABLES IS IMPORTANT: https://disqus.com/admin/universalcode/#configuration-variables*/
        
        var disqus_config = function () {
        this.page.url = "https://blog.xq99.org/posts/6.红黑树的实现/";  // Replace PAGE_URL with your page's canonical URL variable
        this.page.identifier = "红黑树的实现"; // Replace PAGE_IDENTIFIER with your page's unique identifier variable
        };
        
        (function () { // DON'T EDIT BELOW THIS LINE
            var d = document, s = d.createElement('script');
            s.src = 'https://xq773939719.disqus.com/embed.js';
            s.setAttribute('data-timestamp', +new Date());
            (d.head || d.body).appendChild(s);
        })();

    </script>
    <noscript>Please enable JavaScript to view the <a href="https://disqus.com/?ref_noscript">comments powered by Disqus.</a></noscript>

    
    <!-- gitalk评论 -->

    <!-- utteranc评论 -->

    <!-- partial('_partial/comment/changyan') -->
    <!--PC版-->


    
    

    <!-- 评论 -->
</main>
            <!-- profile -->
            
        </div>
        <footer class="footer footer-unloaded">
    <!-- social  -->
    
    <div class="social">
        
    
        
            
                <a href="mailto:773939719@qq.com" class="iconfont-archer email" title=email ></a>
            
        
    
        
            
                <a href="//github.com/xq773939719" class="iconfont-archer github" target="_blank" title=github></a>
            
        
    
        
            
                <span class="iconfont-archer wechat" title=wechat>
                  
                  <img class="profile-qr" src="/assets/wechat.jpeg" />
                </span>
            
        
    
        
            
                <span class="iconfont-archer qq" title=qq>
                  
                  <img class="profile-qr" src="/assets/qq.jpeg" />
                </span>
            
        
    
        
    
        
    
        
            
                <a href="https://www.zhihu.com/people/773939719" class="iconfont-archer zhihu" target="_blank" title=zhihu></a>
            
        
    
        
    
        
    
        
            
                <a href="https://twitter.com/xq773939719" class="iconfont-archer twitter" target="_blank" title=twitter></a>
            
        
    
        
    
        
    
        
    
        
            
                <a href="https://juejin.im/user/2735240659087127" class="iconfont-archer juejin" target="_blank" title=juejin></a>
            
        
    
        
    
        
            
                <a href="https://space.bilibili.com/7076447" class="iconfont-archer bilibili" target="_blank" title=bilibili></a>
            
        
    
        
            
                <a href="https://www.linkedin.com/in/强-许-013122119/" class="iconfont-archer linkedin" target="_blank" title=linkedin></a>
            
        
    
        
    
        
    
        
    

    </div>
    
    <!-- powered by Hexo  -->
    <div class="copyright">
        <span id="hexo-power">Powered by <a href="https://hexo.io/" target="_blank">Hexo</a></span><span class="iconfont-archer power">&#xe635;</span><span id="theme-info">theme <a href="https://github.com/fi3ework/hexo-theme-archer" target="_blank">Archer</a></span>
    </div>
    <!-- 不蒜子  -->
    
    <div class="busuanzi-container">
    
     
    <span id="busuanzi_container_site_pv">PV: <span id="busuanzi_value_site_pv"></span> :)</span>
    
    </div>
    
</footer>
    </div>
    <!-- toc -->
    
    <div class="toc-wrapper" style=
    







top:24vh;

    >
        <div class="toc-catalog">
            <span class="iconfont-archer catalog-icon">&#xe613;</span><span>CATALOG</span>
        </div>
        
    </div>
    
    <div class="back-top iconfont-archer">&#xe639;</div>
    <div class="sidebar sidebar-hide">
    <ul class="sidebar-tabs sidebar-tabs-active-0">
        <li class="sidebar-tab-archives"><span class="iconfont-archer">&#xe67d;</span><span class="tab-name">Archive</span></li>
        <li class="sidebar-tab-tags"><span class="iconfont-archer">&#xe61b;</span><span class="tab-name">Tag</span></li>
        <li class="sidebar-tab-categories"><span class="iconfont-archer">&#xe666;</span><span class="tab-name">Cate</span></li>
    </ul>
    <div class="sidebar-content sidebar-content-show-archive">
          <div class="sidebar-panel-archives">
    <!-- 在ejs中将archive按照时间排序 -->
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    <div class="total-and-search">
        <div class="total-archive">
        Total : 18
        </div>
        <!-- search  -->
        
    </div>
    
    <div class="post-archive">
    
    
    
    
    <div class="archive-year"> 2020 </div>
    <ul class="year-list">
    
    
        <li class="archive-post-item">
            <span class="archive-post-date">12/03</span><a class="archive-post-title" href= "/posts/18.阅读进度/" >阅读进度</a>
        </li>
    
    
        <li class="archive-post-item">
            <span class="archive-post-date">12/03</span><a class="archive-post-title" href= "/posts/13.前端学习网站/" >前端学习网站</a>
        </li>
    
    
        <li class="archive-post-item">
            <span class="archive-post-date">12/03</span><a class="archive-post-title" href= "/posts/14.算法学习网站/" >算法学习网站</a>
        </li>
    
    
        <li class="archive-post-item">
            <span class="archive-post-date">12/03</span><a class="archive-post-title" href= "/posts/15.项目学习网站/" >项目学习网站</a>
        </li>
    
    
        <li class="archive-post-item">
            <span class="archive-post-date">12/03</span><a class="archive-post-title" href= "/posts/16.移动端学习网站/" >移动端学习网站</a>
        </li>
    
    
        <li class="archive-post-item">
            <span class="archive-post-date">12/03</span><a class="archive-post-title" href= "/posts/17.OpenGL学习/" >OpenGL学习</a>
        </li>
    
    
        <li class="archive-post-item">
            <span class="archive-post-date">12/03</span><a class="archive-post-title" href= "/posts/2.内存管理/" >内存管理</a>
        </li>
    
    
        <li class="archive-post-item">
            <span class="archive-post-date">12/03</span><a class="archive-post-title" href= "/posts/3.自我驱动/" >自我驱动</a>
        </li>
    
    
        <li class="archive-post-item">
            <span class="archive-post-date">12/03</span><a class="archive-post-title" href= "/posts/4.计算机网络浅谈/" >计算机网络浅谈</a>
        </li>
    
    
        <li class="archive-post-item">
            <span class="archive-post-date">12/03</span><a class="archive-post-title" href= "/posts/5.Git命令/" >Git命令</a>
        </li>
    
    
        <li class="archive-post-item">
            <span class="archive-post-date">12/03</span><a class="archive-post-title" href= "/posts/6.红黑树的实现/" >红黑树的实现</a>
        </li>
    
    
        <li class="archive-post-item">
            <span class="archive-post-date">12/03</span><a class="archive-post-title" href= "/posts/8.深度探索C++对象模型/" >深度探索C++对象模型</a>
        </li>
    
    
        <li class="archive-post-item">
            <span class="archive-post-date">12/03</span><a class="archive-post-title" href= "/posts/9.iOS开发知识点集合/" >iOS开发知识集合</a>
        </li>
    
    
        <li class="archive-post-item">
            <span class="archive-post-date">12/03</span><a class="archive-post-title" href= "/posts/10.读《如何自学Android》有感/" >读《如何自学Android》有感</a>
        </li>
    
    
        <li class="archive-post-item">
            <span class="archive-post-date">12/03</span><a class="archive-post-title" href= "/posts/11.NPM与Yarn源管理工具/" >NPM与Yarn源管理工具</a>
        </li>
    
    
        <li class="archive-post-item">
            <span class="archive-post-date">12/03</span><a class="archive-post-title" href= "/posts/12.后端学习网站/" >后端学习网站</a>
        </li>
    
    
        <li class="archive-post-item">
            <span class="archive-post-date">12/03</span><a class="archive-post-title" href= "/posts/7.收藏夹/" >收藏夹</a>
        </li>
    
    
        <li class="archive-post-item">
            <span class="archive-post-date">12/03</span><a class="archive-post-title" href= "/posts/1.C++学习的四个层次/" >C++学习的四个层次</a>
        </li>
    
    </div>
  </div>
        <div class="sidebar-panel-tags">
    <div class="sidebar-tags-name">
    
        <span class="sidebar-tag-name" data-tags="RN"><span class="iconfont-archer">&#xe606;</span>RN</span>
    
        <span class="sidebar-tag-name" data-tags="iOS"><span class="iconfont-archer">&#xe606;</span>iOS</span>
    
        <span class="sidebar-tag-name" data-tags="阅读"><span class="iconfont-archer">&#xe606;</span>阅读</span>
    
        <span class="sidebar-tag-name" data-tags="C++"><span class="iconfont-archer">&#xe606;</span>C++</span>
    
        <span class="sidebar-tag-name" data-tags="学习"><span class="iconfont-archer">&#xe606;</span>学习</span>
    
        <span class="sidebar-tag-name" data-tags="环境"><span class="iconfont-archer">&#xe606;</span>环境</span>
    
        <span class="sidebar-tag-name" data-tags="软实力"><span class="iconfont-archer">&#xe606;</span>软实力</span>
    
        <span class="sidebar-tag-name" data-tags="通用"><span class="iconfont-archer">&#xe606;</span>通用</span>
    
        <span class="sidebar-tag-name" data-tags="网络"><span class="iconfont-archer">&#xe606;</span>网络</span>
    
        <span class="sidebar-tag-name" data-tags="HTTP"><span class="iconfont-archer">&#xe606;</span>HTTP</span>
    
        <span class="sidebar-tag-name" data-tags="HTTPS"><span class="iconfont-archer">&#xe606;</span>HTTPS</span>
    
        <span class="sidebar-tag-name" data-tags="数据结构"><span class="iconfont-archer">&#xe606;</span>数据结构</span>
    
        <span class="sidebar-tag-name" data-tags="红黑树"><span class="iconfont-archer">&#xe606;</span>红黑树</span>
    
        <span class="sidebar-tag-name" data-tags="收藏夹"><span class="iconfont-archer">&#xe606;</span>收藏夹</span>
    
        <span class="sidebar-tag-name" data-tags="对象"><span class="iconfont-archer">&#xe606;</span>对象</span>
    
        <span class="sidebar-tag-name" data-tags="Android"><span class="iconfont-archer">&#xe606;</span>Android</span>
    
        <span class="sidebar-tag-name" data-tags="源管理"><span class="iconfont-archer">&#xe606;</span>源管理</span>
    
        <span class="sidebar-tag-name" data-tags="后端"><span class="iconfont-archer">&#xe606;</span>后端</span>
    
        <span class="sidebar-tag-name" data-tags="前端"><span class="iconfont-archer">&#xe606;</span>前端</span>
    
        <span class="sidebar-tag-name" data-tags="算法"><span class="iconfont-archer">&#xe606;</span>算法</span>
    
        <span class="sidebar-tag-name" data-tags="项目"><span class="iconfont-archer">&#xe606;</span>项目</span>
    
        <span class="sidebar-tag-name" data-tags="移动端"><span class="iconfont-archer">&#xe606;</span>移动端</span>
    
        <span class="sidebar-tag-name" data-tags="音视频"><span class="iconfont-archer">&#xe606;</span>音视频</span>
    
        <span class="sidebar-tag-name" data-tags="OpenGL"><span class="iconfont-archer">&#xe606;</span>OpenGL</span>
    
        <span class="sidebar-tag-name" data-tags="网站"><span class="iconfont-archer">&#xe606;</span>网站</span>
    
    </div>
    <div class="iconfont-archer sidebar-tags-empty">&#xe678;</div>
    <div class="tag-load-fail" style="display: none; color: #ccc; font-size: 0.6rem;">
    缺失模块。<br/>
    1、请确保node版本大于6.2<br/>
    2、在博客根目录（注意不是archer根目录）执行以下命令：<br/>
    <span style="color: #f75357; font-size: 1rem; line-height: 2rem;">npm i hexo-generator-json-content --save</span><br/>
    3、在根目录_config.yml里添加配置：
    <pre style="color: #787878; font-size: 0.6rem;">
jsonContent:
  meta: false
  pages: false
  posts:
    title: true
    date: true
    path: true
    text: false
    raw: false
    content: false
    slug: false
    updated: false
    comments: false
    link: false
    permalink: false
    excerpt: false
    categories: true
    tags: true</pre>
    </div> 
    <div class="sidebar-tags-list"></div>
</div>
        <div class="sidebar-panel-categories">
    <div class="sidebar-categories-name">
    
        <span class="sidebar-category-name" data-categories="技术"><span class="iconfont-archer">&#xe60a;</span>技术</span>
    
        <span class="sidebar-category-name" data-categories="技术/移动端"><span class="iconfont-archer">&#xe60a;</span>技术/移动端</span>
    
        <span class="sidebar-category-name" data-categories="技术/博客"><span class="iconfont-archer">&#xe60a;</span>技术/博客</span>
    
        <span class="sidebar-category-name" data-categories="生活"><span class="iconfont-archer">&#xe60a;</span>生活</span>
    
    </div>
    <div class="iconfont-archer sidebar-categories-empty">&#xe678;</div>
    <div class="sidebar-categories-list"></div>
</div>
    </div>
</div> 
    <script>
    var siteMeta = {
        root: "/",
        author: "XQ"
    }
</script>
    <!-- CDN failover -->
    <script src="https://cdn.jsdelivr.net/npm/jquery@3.3.1/dist/jquery.min.js"></script>
    <script type="text/javascript">
        if (typeof window.$ === 'undefined')
        {
            console.warn('jquery load from jsdelivr failed, will load local script')
            document.write('<script src="/lib/jquery.min.js">\x3C/script>')
        }
    </script>
    <script src="/scripts/main.js"></script>
    <!-- algolia -->
    
    <!-- busuanzi  -->
    
    <script async src="//busuanzi.ibruce.info/busuanzi/2.3/busuanzi.pure.mini.js"></script>
    
    <!-- CNZZ  -->
    
    </div>
    <!-- async load share.js -->
    
        <script src="/scripts/share.js" async></script>    
     
    </body>
</html>


